package com.ztom.top100;


/**
 * 不同路径
 * <p>
 * https://leetcode-cn.com/problems/unique-paths/
 *
 * @author ZhangTao
 */
public class Code27UniquePaths {

    public int uniquePaths3(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }

        return process(0, 0, m - 1, n - 1);
    }

    private int process(int i, int j, int ti, int tj) {
        if (i == ti && j == tj) {
            // 到达目标点
            return 1;
        }
        if (i == ti) {
            // 只能往右走
            return process(i, j + 1, ti, tj);
        }
        if (j == tj) {
            // 只能往下走
            return process(i + 1, j, ti, tj);
        }
        // 两边都能走
        return process(i + 1, j, ti, tj) + process(i, j + 1, ti, tj);
    }

    public int uniquePaths2(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        int[][] dp = new int[m][n];
        dp[m - 1][n - 1] = 1;
        for (int j = n - 2; j >= 0; j--) {
            // 最后一个值 dp[m - 1][n - 1] = 1;
//            dp[m - 1][j] = dp[m - 1][j + 1];
            dp[m - 1][j] = 1;
        }
        for (int i = m - 2; i >= 0; i--) {
            // 最后一个值 dp[m - 1][n - 1] = 1;
//            dp[i][n - 1] = dp[i + 1][n - 1];
            dp[i][n - 1] = 1;
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }

        return dp[0][0];
    }

    /**
     * 数组压缩优化
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        int[] dp = new int[n];
        // 最后一行
        dp[n - 1] = 1;
        for (int j = n - 2; j >= 0; j--) {
            dp[j] = 1;
        }
        for (int i = m - 2; i >= 0; i--) {
            // 每行最后一个
//            dp[n - 1] = 1;
            // 从右往左推
            for (int j = n - 2; j >= 0; j--) {
                dp[j] = dp[j] + dp[j + 1];
            }
        }

        return dp[0];
    }
}
